Selepas meninggalkan Polygram, kumpulan Search telah menubuhkan syarikat rakaman sendiri iaitu Go-Search Sdn. Bhd. dan memeterai perjanjian dengan Pacific Music Corporation (kemudian dikenali sebagai BMG Pacific) untuk mengedar semua album mereka sepanjang 1990-an. Mereka kemudiannya merakamkan album pertama mereka di bawah label Go-Search iaitu Fenomena untuk dikeluarkan pada tahun 1989. Album ini juga merupakan album studio pertama mereka yang dikeluarkan dalam bentuk cakera padat, setahun selepas versi kasetnya.[7]

Namun ketika proses rakaman album Fenomena sudah melebihi 50 peratus untuk disiapkan, Search menghadapi ujian getir apabila Hillary Ang keluar dari kumpulan ini untuk mengejar kerjaya solonya. Untuk menyiapkan proses rakaman album yang tergendala itu, Hamzah bin Mohd Taib atau Kid yang sebelum ini telah mencipta nama dengan kumpulan asalnya, Gersang dipilih sebagai gitaris utama Search yang baharu.[7] Penyertaan Kid tepat pada masanya apabila beliau melengkapkan solo untuk tiga lagu yang tidak sempat disiapkan sebelum ini iaitu lagu malar segar Isabella, Purnama & Menara Kesesatan. Sentuhan gitar utama Kid yang 'berhantu' dalam lagu Isabella ternyata mencetuskan satu fenomena yang sangat luar biasa sepertimana judul album ini apabila terjual melebihi 220,000 unit di Malaysia dan melebihi 600,000 unit di Indonesia,[8] sekaligus menjadikan Fenomena sebagai album terbaik dan terlaris yang pernah dikeluarkan oleh Search.

Kejayaan album ini juga menjadikan mereka aktif membuat persembahan secara live, termasuk jelajah Konsert Isabella yang diadakan di Kota Bharu, Alor Star dan Kuala Lumpur pada pertengahan tahun 1989. Persembahan mereka kemudian dilanjutkan ke tahun 1990 yang diadakan di Kuantan dan Jakarta, Indonesia.[4] Tidak cukup dengan itu, Search telah melebarkan sayap apabila semua anggota Search berlakon dalam dua buah filem iaitu Fenomena dan Isabella,[4] di mana kedua-dua filem ini diilhamkan daripada lagu Isabella.[9] Kedua-dua filem ini meletakkan Amy sebagai pelakon utama dan sedikit sebanyak mengundang kontroversi kerana terdapat adegan berciuman.[10]

Search kemudiannya membuka tirai dekad 1990-an dengan mengeluarkan album yang berjudul Karisma.[11] Album tersebut juga terjual laris apabila mencatatkan jualan melebihi 150,000 unit di Malaysia dan 200,000 unit di Indonesia.[8] Sepanjang tahun 1990 juga, Search bersama Ella dan Wings mengadakan jelajah Konsert Revolusi Salem di seluruh negara, di samping menyambungkan jelajah Isabella di Kuantan dan Jakarta seperti yang disebut tadi.[4] Namun tidak lama selepas album Karisma diterbitkan, Nasir Daud meninggalkan Search untuk menubuhkan syarikat penerbitan sendiri iaitu Dangooroos.[11]

Pada tahun 1991, kumpulan Search meraikan ulang tahun ke-10 penubuhannya dengan mengeluarkan album himpunan Sepuluh Tahun yang memuatkan 10 lagu hit lama dan dua lagu baru.[12] Pada tahun ini juga, mereka berpeluang untuk melebarkan sayap populariti mereka merentas benua untuk beraksi di pesta New Music Nights di Cat Club, Bandaraya New York, Amerika Syarikat, pada bulan Julai[13], sebelum kembali ke tanah air untuk Konsert Karisma di Stadium Negara, Kuala Lumpur, sebulan kemudian.[4]

Pada Mei 1992, giliran kumpulan Search menjadi penerbit album sendiri dalam merakamkan album pertama dengan penglibatan M. Nasir sebagai penasihat penerbitan sahaja, bermula dengan album Rampage[14], yang juga diiringi oleh Konsert Rampage di Tapak Pesta Sungai Nibong, Pulau Pinang pada bulan November. Pada tahun yang sama, mereka berkolaborasi dengan Wings untuk menghasilkan album Double Trouble.

Walaupun menikmati populariti yang luar biasa, namun mereka menghadapi rintangan dari pihak media, khususnya penyiar milik negara RTM yang melarang penyanyi lelaki berambut terlalu panjang dari siaran radio dan TV-nya. Oleh itu, pada November 1992, Amy bersama Awie dari kumpulan Wings menerima potongan rambut dari Menteri Penerangan ketika itu, Mohamad Rahmat, agar dapat membuat kemunculan di corong radio dan TV penyiar awam itu.[15] Walau bagaimanapun, RTM kelihatan tidak menepati janjinya, sehingga menerima kecaman dari Amy sendiri untuk mengingatkan mereka pada tahun berikutnya.[16]